#define _CRT_SECURE_NO_WARNINGS
void reverse(int* nums, int left, int right)
{
    while (left <= right)
    {
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
        left++;
        right--;
    }
}
void rotate(int* nums, int numsSize, int k) {
    if (k > numsSize)
    {
        k %= numsSize;
    }
    reverse(nums, 0, numsSize - k - 1);
    reverse(nums, numsSize - k, numsSize - 1);
    reverse(nums, 0, numsSize - 1);
}


class Solution {
public:
    int countPrimes(int n) {
        if (n < 3)
        {
            return 0;
        }
        bool f[n];
        memset(f, 0, sizeof(bool) * n);
        f[0] = 1;
        f[1] = 1;

        for (int i = 2; i < n; i++)
        {
            if (!f[i])
            {
                for (long long j = (long long)i * i; j < n; j += i)
                {
                    f[j] = 1;
                }
            }
        }
        int count = 0;
        for (int i = 2; i < n; i++)
        {
            if (!f[i])
            {
                count++;
            }
        }
        return count;
    }
};